#include <iostream>
#include <cstring>
using namespace std;
unsigned long long n,k,s;
unsigned long long po[1000];
int xn;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i ++)
    {
        long long p,q;
        cin >> n >> k;

        po[0] = 1;
        po[1] = 3;
        for(int i = 2; i < 50; i ++)
        {
            po[i] = (po[i - 1] * po[i - 1]) % k;
        }

        p = (n - 2)/2;
        xn = 1;
        s = 1;
        while(p)
        {
            if(p % 2)
                s = (s * po[xn]) % k;
            p /= 2;
            xn ++;
        }
        if(n == 1)
            cout << 5 % k << endl;
        else if(n % 2 == 0)
            cout << (s * 8) % k << endl;
        else
            cout << (s * 14) % k << endl;
    }
    return 0;
}
